﻿using System.Collections.Generic;
using System.Text;

/*
 * 2021-03-09 JackLee
 * https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string/
 * 解题思路：
 *      遍历字符串数组，如果是相邻的，则将对应位的值置为一个特殊标识，如-1，然后重新开始判断。但是基于这种思路实现竟然相当复杂。
 *      看了题解，刚看到栈就恍然大悟，是啊，栈在字符串或括号匹配等场景下相当便利啊。
 *      StringBuilder可实现类似栈的字符串操作，简单易用。
 * */
namespace RemoveDuplicate
{
    public class Class1
    {
        public string RemoveDuplicates(string S)
        {
            char[] chs;
            Stack<char> stack = new Stack<char>();
            chs = S.ToCharArray();
            for (int i = 0; i < chs.Length; i++)
            {
                if (stack.Count > 0)
                {
                    if (stack.Peek() == chs[i])
                    {
                        stack.Pop();
                        continue;
                    }
                }
                stack.Push(chs[i]);
            }

            StringBuilder sb = new StringBuilder();
            for (int i = stack.Count - 1; i >= 0; i--)
            {
                sb.Insert(0, stack.Pop());
            }
            return sb.ToString();
        }

        /// <summary>
        /// 借助StringBuilder来实现类似栈的操作
        /// </summary>
        /// <param name="S"></param>
        /// <returns></returns>
        public string RemoveDuplicates2(string S)
        {
            StringBuilder sb = new StringBuilder();
            foreach (char c in S)
            {
                if (sb.Length>0&&sb[sb.Length-1]==c)
                {
                    sb.Remove(sb.Length - 1, 1);
                }
                else
                {
                    sb.Append(c);
                }
            }
            return sb.ToString();
        }
    }
}
